﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class HanRiver
    {
        public HanRiver()
        {
            int testCount = Int32.Parse(TestConsole.ReadLine());

            long[] divisors = new long[1000001];
            long[] min = new long[1000001];
            for (int i = 2; i < divisors.Length; i++)
            {
                for (int j = i * 2; j < min.Length; j += i)
                {
                    if(divisors[j] == 0)
                    {
                        min[j] = i;
                    }
                    divisors[j]++;
                }
            }
            for (int testCase = 1; testCase <= testCount; testCase++)
            {
                string[] input = TestConsole.ReadLine().Split(' ');
                int m = Int32.Parse(input[0]);
                int n = Int32.Parse(input[1]);
                int count = 0;
                for (int i = 2; i < m; i++)
                {
                    if (divisors[i] == divisors[m] && min[i] >= n)
                    {
                        count++;
                    }
                }
                Console.WriteLine("Case #" + testCase + ": " + count);
            }
        }
    }
}
